package my.sort.cmp;

import my.sort.Sort;

/**
 * 快速排序
 *
 * @author AJun
 * @date 2020/9/19
 */
public class QuickSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    protected void sort() {
        sort(0, array.length);
    }

    /**
     * 对 [begin, end) 范围的元素进行快速排序
     *
     * @param begin 开始索引
     * @param end   结束索引
     */
    private void sort(int begin, int end) {
        if (end - begin < 2) {
            return;
        }

        // 确定轴点位置 O(n)
        int mid = pivotIndex(begin, end);
        // 对子序列进行快速排序
        sort(begin, mid);
        sort(mid + 1, end);
    }

    /**
     * 构造出 [begin, end) 范围的轴点元素 (轴点构造)
     *
     * @param begin 开始索引
     * @param end   结束索引
     * @return 轴点元素的最终位置
     */
    private int pivotIndex(int begin, int end) {
        // 随机选择轴点元素，使得轴点左右元素数量尽可能保持均匀，范围 [begin, end)
        swap(begin, (int) (begin + Math.random() * (end - begin)));
        // 备份 begin 位置的元素(轴点元素)
        T pivot = array[begin];
        // end 指向最后一个元素
        end--;

        // 轴点元素构造
        while (begin < end) {
            while (begin < end) {
                if (cmp(pivot, array[end]) < 0) {
                    // 右边元素大于轴点元素
                    end--;
                } else {
                    // 右边元素小于等于轴点元素
                    array[begin++] = array[end];
                    break;
                }
            }

            while (begin < end) {
                if (cmp(pivot, array[begin]) > 0) {
                    // 左边元素小于轴点元素
                    begin++;
                } else {
                    // 左边元素大于等于轴点元素
                    array[end--] = array[begin];
                    break;
                }
            }
        }

        // 将轴点元素放到最终位置
        array[begin] = pivot;
        // 返回轴点元素
        return begin;
    }

}
